iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 11
1
Software Development

從LeetCode學演算法系列 第 11

[Day 11] 從LeetCode學演算法 - 0083. Remove Duplicates from Sorted List (Easy)

  • 分享至 

  • xImage
  •  

目標:
本題的目標在於學習LinkedList的一些基本操作。

原題:

Question:
Given a sorted linked list, delete all duplicates such that each element appears only once.
Example 1:
Input: 1->1->2
Output: 1->2
Example 2:
Input: 1->1->2->3->3
Output: 1->2->3

分析/解題:
題目給定一個已排序好的linked list,要求將所有重複的node皆刪除,
使得每個元素均只出現一次。

這題也算是比較簡單的linked list類型,只要確定連接正確的話並不難解。
由於已經排序過的原因,所有會重複的元素值均會相鄰,
那麼我們所要做的就是遇到重複時總共只保留一個就好了
保留哪一個呢?當然是保留第一個囉!

我們可以先宣告一個ListNode,命名為ite用來做為iterator(迭代器),
每次取得ite的下一個node(命名為tmp)做為暫存。
接下來開始一路往下尋找,如果ite和tmp前後值相等時,
就讓tmp開始往下一直走到底部(表示後面值都一樣)或者找到下一個不同的值
對於前者的狀況而言,表示結束,tmp會指到null(或None),
只要將ite.next指向到tmp即可。

對於後者的狀況,這時候tmp的位置就在下一個相異值的點
像是1->2->2->2->3->4這樣子,從ite在碰到第一個2以後,
tmp會一路找到3的位置,所以我們只要將ite.next指向到tmp
即可將第一個2接到3的位置,從而中間的部分就等於被我們刪去了。

討論完兩者狀況後,我們會發現無論是哪一種,
結果都會是將ite.next指向到tmp,
最後要記得ite本身要遞移到下一個開始找的位置,
所以我們還需要將tmp的位置交給ite。

Java:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode ite = head;
        while(ite != null) {
            ListNode tmp = ite.next;
            while (tmp != null && ite.val == tmp.val) tmp = tmp.next;
            ite.next = tmp;
            ite = tmp;
        }
        return head;
    }
}

以Python的部分來說,還記得判斷式可以直接適用於if的話,
就可以寫得看起來簡潔一些。

Python:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteDuplicates(self, head: 'ListNode') -> 'ListNode':
        ite = head
        while ite:
            tmp = ite.next
            while tmp and ite.val == tmp.val:
                tmp = tmp.next
            ite.next = tmp
            ite = tmp        
        return head

面試實際可能會遇到的問題:
「時間/空間複雜度?」
(O(N), O(1))

其它應該沒什麼好問的,至少我沒想到XD
這篇主要是協助讀者再熟悉一下這些連接/斷開的操作。

從LeetCode學演算法,我們下次見囉,掰~

下篇預告:
0089. Gray Code (Medium)


上一篇
[Day 10] 從LeetCode學演算法 - 0070. Climbing Stairs (Easy)
下一篇
[Day 12] 從LeetCode學演算法 - 0089. Gray Code (Medium)
系列文
從LeetCode學演算法30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言